package com.leetcodehot.problems;

import java.util.Arrays;

public class problems2439 {
    /**
     * 给你一个下标从 0 开始的数组 nums ，它含有 n 个非负整数。
     * <p>
     * 每一步操作中，你需要：
     * <p>
     * 选择一个满足 1 <= i < n 的整数 i ，且 nums[i] > 0 。
     * 将 nums[i] 减 1 。
     * 将 nums[i - 1] 加 1 。
     * 你可以对数组执行 任意 次上述操作，请你返回可以得到的 nums 数组中 最大值 最小 为多少。
     */
    public boolean isOk(int[] nums, int x) {
        //从右边往左推
        int n = nums.length;
        long val = 0;
        for (int i = n - 1; i > 0; i--) {
            if (val + nums[i] > x) {
                val = val + nums[i] - x;
            } else {
                val = 0;
            }
        }
        return val + nums[0] <= x;
    }

    public int minimizeArrayValue(int[] nums) {
        int n = nums.length;
        int max = 0;
        for (int num : nums) {
            max = Math.max(max, num);
        }

        int left = 0;
        int right = max;
        while (left + 1 < right) {
            int mid = left + (right - left) / 2;
            //判断mid是否可以
            if (isOk(nums, mid)) {
                right = mid;
            } else {
                left = mid;
            }
        }
        return right;
    }
}
